The present invention relates to an inter-network connecting devise.which transmits a message having a protocol according to a plurality of protocol layers respectively defined as a physical layer to upper layers. The inter-network connecting device is disposed between plural networks and has a function of connecting these networks to each other at a specific protocol layer, and which is used for transmitting a message including its destination address data from a sender to its destination which are in different networks. The invention relates particularly to a network connecting apparatus which makes it possible to efficiently perform such processes as a transmission path determining process and the like in a network connecting apparatus by reducing looping processes or replacing them with comparatively simple processes mainly with regard to such processes which have been up to now complicated and time-consuming as a process of extracting a network address or a subnetwork address from the destination address of a received message (received frame) and the like, and thereby makes it possible to improve the processing speed and make a cost reduction by simplification of the hardware to be used, and be formed into hardware as a whole.
Such a telephone-network built for the purpose of intercommunication by voice as a public line of telephone communication, a leased line, and the like is restricted in transmission quality and transmission speed when being used in data communication. Therefore, public digital data networks more adaptive in such characteristics specific to data communication as data traffic characteristics and the like are being built up in various countries including Japan. The public digital data network uses transmission paths and switching systems for digital signals, and some services by circuit switching networks or packet switching networks are provided in Japan. For international connection also, international standardization is promoted by the International Telegraph and Telephone Consultative Committee (CCITT), and at present has been almost provided as recommendations (X-series Recommendations) related to such new data networks as circuit switching systems, packet switching systems, leased digital lines, and the like.
In recent years, a network called a Local Area Network (LAN) has been widely used for the purpose of sharing such information (data) as a database or the like and peripheral apparatuses. The LAN is a network for connecting digital apparatuses such as computers, communication terminals and the like distributed in such a limited specific area as an office, a factory, a laboratory, a university and the like, and has a kind of switching function. In such a LAN also, standardization of protocols and the like has been performed by Committee 802 of the Institute of Electrical and Electronic Engineers (IEEE), the International Standardization Organization (ISO) and the like.
The reference model for the Open Systems Interconnection (OSI) being applied to a public digital data network and the above-mentioned LAN protocol standardized by IEEE are defined by plural protocol layers which are defined as a physical layer to upper layers. Protocols used widely in Wide Area Networks (WAN) or other LANs and the like also are generally defined according to plural protocol layers. In such a way, most network protocols are defined according to plural protocol layers.
Plural networks such as LANS, WANs, public digital networks, or the like have been connected with one another up to now. For example, even networks which have at least a few protocol layers different from one another out of a plurality of protocol layers to define a protocol for a message to be transmitted have been connected with one another up to now.
Hereupon, an inter-network connecting device for connecting with each other through the second layer two networks which have the same Media Access Control (MAC) layer which is the second layer for OSI is called a bridge or the like. An inter-network connecting device for connecting to one another a plurality of networks which are different from one another in the first to seventh layers for OSI is called a gateway or the like. And an inter-network connecting device, as referred to as an embodiment described later in this application, for connecting to one another through the third layer a plurality of networks which are different from one another in the first to third layers for OSI is called a router or the like.
An inter-network connecting device which the present invention considers as an object is not limited to a router in an embodiment described later, but can be applied also to a bridge and a gateway described above for example. And also networks which an inter-network connecting device according to the present invention connects to one another are not limited to the above-mentioned specific LANS, but may be various LANS, WANs, public digital data networks.
Hereupon, an inter-network connecting device used up to now for connecting LANs to one another, particularly an Interment Protocol (IP) router is described in detail with regard to the present invention.
An IP router performs a process for determining a transmission path of a received frame (hereinafter referred to as an IP routing process) on the basis of the destination IP address in the IP header contained in the received frame. Such an IP routing process is performed as extracting various address components, particularly the network address of the destination IP address.
However, a general inter-network connecting device also performs a series of processes (called a routing process) for transferring a received message to an appropriate network at the destination side to be connected to the said inter-network connecting device as extracting various address components from the destination address in the received message and performing a control according to the various address components.
The destination IP address of 32 bits is composed of a total of three fields, namely, a class bit field, a network address bit field and a host address bit field, as shown in FIG. 1. Each of the fields is composed in this order from the most significant bit (MSB) side to the least significant bit (LSB) side of the IP address of 32 bits. As shown in FIG. 1, the number of bits of a network address bit field, the number of bits of a host address bit field as well as the number of bits of a class bit field are determined according to the address classes A to C indicated by the class bits.
As shown in FIG. 1, first, in case that the MSB of an IP address of 32 bits is xe2x80x9c0xe2x80x9d, an address class of xe2x80x9cAxe2x80x9d (hereinafter referred to as class A) is shown in the class bit field. In this case the network address bit field becomes 7 bits and the host address bit field becomes 24 bits. In case that the first two bits from the MSB of an IP address are xe2x80x9c10xe2x80x9d, an address class of xe2x80x9cBxe2x80x9d (referred to as class B) is shown in the class bit field. In this case the network address bit field becomes 14 bits and the host address bit field becomes 16 bits. And in the first three bits from the MSB of an IP address are xe2x80x9c110xe2x80x9d, an address class of xe2x80x9cCxe2x80x9d (referred to as class C) is shown in the class bit field. In this case the network address bit field becomes 21 bits and the host address bit field becomes 8 bits.
Said network address indicates the address of a network on the Internet. The network address is represented with said class bits and said network address bits. A host address indicates the address of an individual host in a network indicated by said network addresses. The host address is represented with said host address bits.
Said IP router is disposed between plural networks and checks the destination IP address in the IP header contained in a received frame received from a network. The IP router checks particularly the network address in a destination IP address and when the IP network address is a network connected to a port of that IP router (its own port), the IP router extracts the MAC address from the host address of the IP address and transmits the frame to the corresponding host. On the other hand, in case that the network address in the IP address indicates an address other than a network to be connected to its own port, the IP router relays the received frame to another port.
When extracting a network address from an IP address of 32 bits, the IP router processes an IP address mask of a received frame. The mask process is performed by performing the AND operation of bits corresponding to each other between the IP address and a specified address mask. Here, an address mask is data of 32 bits like an IP address. Particularly, in an address mask for extracting a network address, bits at the same bit positions of the class bit and network address bit fields of an IP address are respectively xe2x80x9c1xe2x80x9d, and the other bits at the same bit positions as the host address bit field of the IP address are xe2x80x9c0xe2x80x9d.
Said address mask is used for extracting various address components such as a network address and the like by making the logical AND of it with such a destination address as an IP address or the like. Therefore, when a bit of an address mask is xe2x80x9c1xe2x80x9d, the bit of a specific address component is extracted at that bit position, and hereinafter setting a bit as an object of extraction in such a way is expressed as xe2x80x9cmaskingxe2x80x9d. On the other hand, when a bit of an address mask is xe2x80x9c0xe2x80x9d, such a specific address component is not extracted, and setting a bit as non-object of extraction in such a way is expressed as xe2x80x9cno masking (ignoring)xe2x80x9d.
If an IP address has one of only three classes A to C, a network address bit field also is one of only three fields, and accordingly it will do also to prepare only three kinds of address masks to be used in extracting network address bits. In case of actually extracting a network address, it will do to determine what class its address class is of classes A to C on the basis of the first one to three bits from the MSB of an IP address, select one of three kinds of address masks according to the determined class, and extract the corresponding network address bits by means of the selected address mask, and therefore it is possible to comparatively simply and automatically perform this network address extracting process.
In recent years, however, as the number of IP addresses becomes short, it is required to more effectively make good use of addresses to be represented by 32 bits. Thus, a multi-protocol process has been performed which uses the first several bits of a host address bits in addressing a subnetwork obtained by dividing a network into plural parts in consideration of treating said first several bits in the same way as network address bits.
In case that said IP router is provided between such multi-protocol subnetworks, it is necessary to perform a subnetwork address extracting process similar to said network address extracting process using an address mask and correctly relay a frame according to a subnetwork address extracted from the received frame. In order to extract a subnetwork address in such a manner, it is necessary to provide an address mask to be exclusively used.
Therefore, in order to cope with the network address or subnetwork address of a network to be connected, a recent IP router is provided with a table of not only IP addresses but also address masks corresponding to these IP addresses. Using such a table, the IP router extracts a network address or a subnetwork a address in the IP address of a received frame. A method of using a table in such a manner is logically simple and easy to understand, but has a complicated problem as shown in the following in practical processing.
That is to say, in case that an IP address does not have a subnetwork address field, it is possible to determine an address class based on the first one to three bits from the MSB of the IP address contained in a received frame and obtain uniquely an address mask for extracting a network address. However, in case that an IP address has a subnetwork address field, it is not possible to obtain uniquely an address mask for extracting a subnetwork address or a network address. In an IP router, therefore, it is generally necessary to perform one of the following processes.
A1. A process of comparing with each other network addresses in a table contained in an IP router (network addresses obtained by mask-processing IP addresses in the table with address masks) and the IP address in a received frame, selecting an entry having the most number of bits coincident with the corresponding bits of the IP address among all entries in the table, and using the network address of the entry as the destination address.
A2. A process in which a masking process is performed treating as xe2x80x9c1xe2x80x9d all bits of an address mask corresponding to the IP address in a received frame and the result is compared with network addresses in the table; and in case that there is not a coincident address, the result obtained by setting the LSB as xe2x80x9c0xe2x80x9d is compared again with the network addresses in the table; and then in case that there is not a coincident address again, the result obtained by setting the bit next to the LSB also as xe2x80x9c0xe2x80x9d is compared again with the network addresses in the table; and in this manner, the results obtained by setting bit by bit the bits of the address mask as xe2x80x9c0xe2x80x9d from the LSB side are compared with the network addresses in the table until a coincident address is found.
As shown in the above-mentioned processes A1 and A2, in case of a multi-protocol process where there is a subnetwork field in an IP address, there has been up to now a problem that a process for extracting a network address becomes very complicated and the processing time becomes long. And such a process has a problem that it can be generally processed by only software and it is very difficult to form such a process into hardware. Moreover, to be provided with a table in which an address of 32 bits can be retrieved as it is even after extracting a network address is uneconomical due to increasing the number of data in the table. Accordingly, a fact that a special logical circuit needs to be provided at the outside and such a measure as a hash method of retrieving data in a tree-like form by means of a hash function is required results in imposing a great load on software.
Thus a high-performance central processing unit (CPU) is generally used in order to shorten the processing time. Even if a high-performance CPU is used, however, shortening of the processing time is limited and such a process of extracting a network address or a process of performing a table retrieval to be performed after the extracting process has been a bottleneck in a relay process in an IP router.
Even utilization of a content addressable memory (CAM) for the purpose of simplifying the process has not been able to make the best use of its merit, since due to variation of the bit length of a mask, a CAM is required for each corresponding bit length.
The present invention has been made in order to solve the above-mentioned existing problems, and has an object of making it possible to efficiently perform such various processes as a transmission path determining process and the like in a network connecting apparatus to cope with a multi-protocol system by reducing looping processes or replacing them with comparatively simple processes mainly with regard to such processes up to now complicated and time-consuming as a process of extracting a network address or a subnetwork address from the destination address of a received message (received frame) and the like, and thereby improving the processing speed and attaining a cost reduction thanks to simplifying the hardware to be utilized.
The present invention solves the above-mentioned problems by providing an inter-network connecting device which is disposed between plural networks each of which transmits a message having a protocol according to a plurality of protocol layers respectively defined as a physical layer to upper layers and has a function of connecting these networks to each other at a specific protocol layer, and which is used for transmitting a message including its destination address data from a sender to its destination which are in different networks, said inter-network connecting device comprising;
a mask processing part which generates according to the destination address an address mask for extracting various address components from the said destination address in a message received by the said inter-network connecting device and outputs a retrieval reference control address obtained by processing said destination address with said generated address mask, and
a transmission control information generating part for generating a transmission control information to be used in transmitting a message to a network at the destination side in said inter-network connecting device on the basis of said retrieval reference control address; and
relaying the received message to an appropriate network at the destination side, said appropriate network being connected to said inter-network connecting device, according to said transmission control information.
The present invention makes it possible to do without looping processes and realize said inter-network connecting device with a high-speed hardware by making said mask processing part be composed of;
an address mask table for storing as address entry data a plurality of pairs each of which is a pair of a reference entry address and a reference entry mask showing whether or not individual bits of said reference entry address take part in extracting said various address components,
entry data comparators of the same number as the number of said address entry data for judging an address coincidence between the reference entry addresses and said destination address as masking said corresponding address entry data with the reference entry mask,
an address mask generating part for generating said address mask to be actually used as synthesizing a reference entry mask of address entry data corresponding to the respective entry data comparators which have judged to have an address coincidence out of these entry data comparators, and
a masking circuit for generating and outputting said retrieval reference control address by processing said destination address with said address mask. However, part of the looping processes may be left.
Moreover, in the present invention, said address mask generating part selects a reference entry mask which has the most number of bits designated to take part in extracting said various address components out of reference entry masks of address entry data corresponding to the respective entry data comparators which have been judged to have an address coincidence among said entry data comparators, and outputs this reference entry mask as said address mask.
And the present invention can make small-sized said address mask table by shortening the bit length of each of a plurality of address entry data, particularly the bit length of each of said reference entry masks which exist in said address mask table, through making said reference entry mask indicate individual bits of said reference entry address taking part in extracting said various address components by means of data showing a mask length.
The present invention makes it possible to also cope with variety of masking processes for masking the destination address which processes are necessary in case of relaying data frames to both of a host computer directly connected to said inter-network connecting device and a host computer connected through another inter-network connecting device to the said inter-network connecting device, by providing said inter-network connecting device in which said address entry data has an all-bit effective flag and said entry data comparator has an all mask bit compulsorily setting circuit for realizing a function of compulsorily setting as xe2x80x9ceffectivexe2x80x9d all bits of a reference entry mask used by said address mask generating part in case that said all-bit effective flag of said address entry data corresponding to said entry data comparator indicates xe2x80x9ceffectivexe2x80x9d when judging said address coincidence.
And the present invention attempts to improve said transmission control information generating part in operating efficiency and operating speed by making said transmission control information generating part be provided with a content addressable memory for storing said transmission control information and generate said transmission control information using said retrieval reference control address as retrieval data of said content addressable memory and using a coincidence address output of said content addressable memory.
And the present invention attempts to improve said transmission control information generating part in operating efficiency and operating speed by making said transmission control information generating part be provided with a content addressable memory for storing said transmission control information and generate said transmission control information using said retrieval reference control address as retrieval data of said content addressable memory and using data not used in the retrieval data indicated by an address at which a data coincidence has been detected in said content addressable memory.
And the present invention makes it possible to reduce the number of said address entry data and facilitate coping with a wide range of networks, in case that an address coincidence has not been detected in any of plural entry data comparators provided by the same number as the number of said address entry data, by recognizing the address class of said destination address based on judgment of the bit string of said destination address, generating a bit string indicating bit by bit whether or not a bit takes part in extracting said various address components on the basis of said address class, and using said bit string as said address mask.
The present invention makes it possible to solve said problems and realize the solving means with hardware by providing an inter-network connecting device which comprises;
a mask register group for storing a plurality of different address masks for extracting various address components from said destination address in a message received by said inter-network connecting device one after another in order of decreasing the number of digits to be masked,
a counter used for selecting a plurality of address masks to be stored in said mask register group in order of decreasing the number of digits to be masked,
a content addressable memory which stores as retrieval data the respective addresses of transmission paths indicated by said various address components, retrieves said address coincident with said destination address as using an address mask selected by said counter, and, in case that there is an coincident address, outputs a hit signal and outputs as a hit address signal a content addressable memory address where the coincident retrieval data is stored, and
a retrieval sequence which controls initialization of said counter and controls a retrieval operation using said content addressable memory which retrieval operation is performed until said hit signal is outputted as selecting an address mask by searching address masks in order of decreasing the number of digits to be masked through counting digit by digit the address digits by means of said counter; and
relays the received message to an appropriate network at the destination side, said appropriate network being identified on the basis of said hit address signal and being to be connected with the said inter-network connecting device.
And the present invention makes it possible to improve the processing speed by means of parallel execution of a checking process by providing said inter-network connecting device further comprising plural sets of said address mask groups, said counters, and said content addressable memories, in which said plural address mask groups respectively store one by one in rotation said plural different address masks in order of decreasing the number of digits to be masked, and said plural content addressable memories store the same retrieval data as one another.
Operation of the present invention is described in brief with reference to the drawings in the following.
First, it is assumed that an inter-network connecting device of the present invention is disposed between plural networks each of which transmits a message, for example, a received frame having a protocol according to a plurality of protocol layers in which a physical layer to upper layers have been defined. And the inter-network connecting device of the present invention has a function of connecting these networks to each other at a specific protocol layer and is used for transmitting a message containing data of its destination address from a sender to its destination which are in different networks from each other.
As shown in FIG. 2, an example of an inter-network connecting device of the present invention is basically provided with a mask processing part 10 and a transmission control information generating part 30.
First, the mask processing part 10 generates an address mask for extracting various address components from said destination address in a message received by said inter-network connecting device according to said destination address, and outputs a retrieval reference control address obtained by processing said destination address with said generated address mask. This retrieval reference control address corresponds to a network address or a subnetwork address extracted from the destination IP address of the received frame described above in the prior art. The mask processing part 10 of the invention is characterized by that it generates an address mask for extracting various address components from said destination address according to said destination address. That is to say, it generates an address mask not only according to class bits like said IP router of the prior art, but more positively according to said destination address.
Next, the transmission control information generating part 30 generates a transmission control information to be used in transmitting a message to the destination network by said inter-network connecting device on the basis of said retrieval reference control address outputted by said mask processing part 10.
For example, in case that said retrieval reference control address outputted by said mask processing part 10 is a network address or a subnetwork address as described above in the prior art, a transmission control information outputted by said transmission control information generating part may be the port number or MAC address of a port connected to a network to which a message received in said network connecting apparatus is relayed and transmitted. Or, for example, in case that said retrieval reference control address outputted by said mask processing part 10 is a preliminary signal used in a preprocess for generating a network address or a subnetwork address described as the prior art, said transmission control information outputted by said transmission control information generating part 30 may be a network address or a subnetwork address.
In this way, in extracting a network address or a subnetwork address as described in the prior art from the destination address in a received message (for example, a received frame) or further generating a port number or MAC address in a network to which a message (frame) to be transmitted is to sent, the present invention can perform an efficient process by using a unique two-stage composition of a mask processing part 10 and a transmission control information generating part 30 as described above. And in particular, the present invention can also make the mask processing part 10 improve a formerly difficult process of generating an address mask thanks to its unique process of generating an address mask for extracting various address components from a destination address according to the destination address.
The present invention is not limited to this, but a content addressable memory may be used in said transmission control information generating part 30. Since the present invention has particularly a two-stage composition of a mask processing part 10 and a transmission control information generating part 30 as described above, it can easily use such a content addressable memory. In case of using such a content addressable memory, since the transmission control information generating part 30 can efficiently generate a network address or a subnetwork address, a port number or MAC address of a related network and the like according to inputted signals mainly with regard to various address components extracted by said mask processing part 10 from the destination address of a received message, it is possible to improve the processing speed and make a cost reduction thanks to simplification of the hardware used in the system.
Another example of an inter-network connecting device of the present invention is basically provided with a mask register group 122, a counter 124, a CAM 116, and a retrieval sequencer 112, as shown in FIG. 3.
The mask register group 122 stores, in order of decreasing the number of digits to be masked, plural different address masks for extracting various address components from the destination IP addresses IP of messages received by said inter-network connecting device. That is to say, the mask register group 122 stores plural different address masks in order of decreasing the number of digits to be masked, namely, in order of increasing the number of digits not to be masked.
Said counter 124 is used for selecting plural address masks stored in said mask register group 122 in order of decreasing the number of digits to be masked. When said counter 124 is initialized in count value by a retrieval initializing signal INT, it outputs a selection signal SE indicating an address mask having the most number of digits to be masked, namely, the least number of digits not to be masked. And said counter 124 changes its count value by xe2x80x9c1xe2x80x9d, namely, increments (increases the value by xe2x80x9c1xe2x80x9d) or decrements (decreases the value by xe2x80x9c1xe2x80x9d) each time a retrieval start signal ST is inputted. By this, each time a retrieval start signal ST is inputted, said counter 124 outputs a selection signal SE for selecting an address mask in order of decreasing the number of digits to be masked.
Said CAM 116 stores as retrieval data the respective addresses of transmission paths indicated by various address components. The address of a transmission path is an address showing a network at the destination side of said inter-network connecting device or another inter-network connecting device, and corresponds to a network address or a subnetwork address extracted from the destination IP address of a received frame, for example, as described above. Said CAM 116 retrieves an address as described above which is coincident with the destination IP address IP and stored in said CAM 116, using a selected mask signal SM (address mask) which has been selected by a selection signal SE outputted from said counter 122 and is outputted from the mask register group 122. In case that there is a coincident address in such a retrieval, said CAM 116 outputs a hit signal HIT showing that there is said coincidence to at least the retrieval sequencer 112, and outputs as a hit address signal HA a content addressable memory address at which the coincident retrieval data is stored. This retrieval data is an address showing a corresponding transmission path as described above.
When a destination IP address IP is inputted from the outside, said retrieval sequencer 112 first controls initialization of the counter 124 by outputting a retrieval initializing signal INT. After this, said retrieval sequencer 112 outputs retrieval start signals ST one by one to the counter 124 until a hit signal HT is inputted from the CAM 116. An inter-network connecting device of the present invention inputs thus retrieval start signals ST one by one into the counter 124, counts (counts up or counts down) them one by one with said counter 124, and obtains a selected mask signal SM obtained by selecting it from address masks stored in the mask register group 122 in order of decreasing the number of digits to be masked, and performs a retrieval operation in the CAM 116 as using said selected mask signal SM until a hit signal HT is outputted.
According to such a composition as shown in FIG. 3 as described above, namely, according to the composition consisting of the mask register group 122, the counter 124, the CAM 116 and the retrieval sequencer 112, it is possible to obtain a hit address signal HA corresponding to an inputted destination IP address IP. And it is possible to recognize an appropriate network and the like at the destination side which is identified on the basis of said hit address signal HA and is connected to the said inter-network connecting device. Therefore, said inter-network connecting device can transfer a received message to an appropriate network at the destination side to be connected to said inter-network connecting device as using a hit signal HT obtained in such a way.
Accordingly, the present invention makes it possible to efficiently perform such processes as a transmission path determining process and the like in an inter-network connecting device by reducing looping processes or replacing them with comparatively simple processes mainly with regard to such processes which have been up to now complicated and time-consuming as a process of extracting a network address or a subnetwork address from the destination address of a received message (received frame) and other processes, and thereby makes it possible to improve the processing speed, perform a cost reduction by simplifying the hardware to be utilized, and form the whole apparatus into hardware.